{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Column Generation for the Cutting Stock Problem\n",
    "\n",
    "## Objectives and Prerequisites\n",
    "\n",
    "In this notebook, you will:\n",
    "\n",
    "1. Learn about the Cutting Stock Problem, a classical problem from the Integer Programming (IP) literature.\n",
    "2. Discover how delayed column generation can be implemented in Gurobi to solve this problem more efficiently.\n",
    "\n",
    "This modelling example is at the advanced level. To fully understand the content of this notebook, the reader should be familiar with the following:\n",
    "\n",
    "- Object-Oriented Programming.\n",
    "- The Knapsack Problem.\n",
    "- Delayed column generation as a decomposition technique.\n",
    "\n",
    "-----\n",
    "\n",
    "## Motivation\n",
    "\n",
    "Despite the great advancements that we've seen in mathematical optimization solver technology, some problems are still challenging to solve due to their large number of variables or constraints. Decomposition techniques — such as delayed column generation or Benders decomposition — apply the principle of \"divide and conquer\" to tackle these challenging problems.\n",
    "\n",
    "Delayed column generation is typically used with large problems, which have so many variables that it's not possible to consider all of them explicitly. Experience with large problems indicates that, usually, most of these variables never enter the basis. Therefore, only a subset of these variables need to ever be considered when solving the problem. Delayed column generation exploits this fact to only generate variables (i.e. columns) that have the potential to improve the objective function. It's interesting to note that generating a column in the primal formulation amounts to adding a constraint to its dual. Thus, you can think of this technique as a cutting plane method in the dual space.\n",
    "\n",
    "Delayed column generation has been successfully applied to many problems such as crew scheduling, vehicle routing, the capacitated p-median problem, and the Cutting Stock Problem. We will use the latter to illustrate how this technique can be implemented in the Gurobi-Python interface.\n",
    "\n",
    "-----\n",
    "\n",
    "## Problem Description\n",
    "\n",
    "The Cutting Stock Problem deals with the problem of cutting stock material with the same, fixed width — such as paper rolls — into smaller pieces, according to a set of orders specifying both the widths and the demand requirements, so as to minimize the amount of wasted material.\n",
    "\n",
    "![image](./csp_ex.png)\n",
    "\n",
    "-----\n",
    "\n",
    "## Solution Approach\n",
    "\n",
    "Mathematical programming is a declarative approach where the modeler formulates a mathematical optimization model that captures the key aspects of a complex decision problem. The Gurobi Optimizer solves such models using state-of-the-art mathematics and computer science.\n",
    "\n",
    "A mathematical optimization model has five components, namely:\n",
    "\n",
    "- Sets and indices.\n",
    "- Parameters.\n",
    "- Decision variables.\n",
    "- Objective function(s).\n",
    "- Constraints.\n",
    "\n",
    "First, we present a naïve IP that doesn't scale well because its linear relaxation is not tight. Then, we introduce a Full Master Problem that explicitly enumerates all possible cut patterns, which turns out to be amenable to delayed column generation.\n",
    "\n",
    "### Naïve IP\n",
    "\n",
    "#### Sets and Indices\n",
    "\n",
    "$i \\in \\text{Stock}=\\{1,2,\\dots, N\\}$: Set of available stock material units.\n",
    "\n",
    "$j \\in \\text{Pieces}$: Set of final pieces.\n",
    "\n",
    "#### Parameters\n",
    "\n",
    "$N \\in \\mathbb{N}$: Upper bound for the number of stock material units that can be used.\n",
    "\n",
    "$\\text{Stock_length} \\in \\mathbb{R}^+$: Length of any stock material unit.\n",
    "\n",
    "$\\text{Piece_length}_j \\in \\mathbb{R}^+$: Length of final piece $j$.\n",
    "\n",
    "$\\text{Requirement}_j \\in \\mathbb{N}$: Demand requirement of final piece $j$.\n",
    "\n",
    "#### Decision Variables\n",
    "\n",
    "$\\text{use}_i \\in \\{0,1\\}$: 1 if stock material unit $i$ is used; 0 otherwise.\n",
    "\n",
    "$\\text{cut}_{i,j} \\in \\mathbb{N}$: Number of pieces of type $j$ cut out from stock material unit $i$.\n",
    "\n",
    "#### Objective Function\n",
    "\n",
    "- **Material Consumption:** Minimize the number of stock material units used.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\text{Min} \\sum_{i \\in \\text{Stock}}{\\text{use}_i}\n",
    "\\tag{1.0}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "#### Constraints\n",
    "\n",
    "- **Satisfy Demand:** Total number of final pieces of type $j$ obtained must satisfy its demand requirement.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\sum_{i \\in \\text{Stock}}{\\text{cut}_{i,j}} \\geq \\text{Requirement}_j \\quad \\forall j \\in \\text{Pieces}\n",
    "\\tag{1.1}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "- **Capacity:** Total length of the pieces cut out from stock material unit $i$ cannot exceed its length.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in \\text{Pieces}}{\\text{Piece_length}_j \\cdot \\text{cut}_{i,j}} \\leq \\text{Stock_length} \\cdot \\text{use}_i \\quad \\forall i \\in \\text{Stock}\n",
    "\\tag{1.2}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "- **Symmetry breaking:** Stock material unit $i+1$ cannot be used if the previous unit $i$ wasn't. Note that this constraint set is not needed for correctness, but certainly helps to reduce the search space.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\text{use}_{i+1} \\leq \\text{use}_i \\quad \\forall i \\in \\text{Stock} \\setminus \\{N\\}\n",
    "\\tag{1.3}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "### Full Master Problem\n",
    "\n",
    "Now, instead of focusing on which stock material unit a particular piece is to be cut from, we consider all possible patterns (potentially generating multiple pieces of different widths) that can be used to cut from a stock material unit. The task is now to find how many times a particular pattern should be used.\n",
    "\n",
    "#### Sets and Indices\n",
    "\n",
    "$p \\in \\text{Patterns}$: Set of all possible cutting patterns, whose size grows exponentially with the number of final pieces. Note that each of these patterns implicitly considers the lengths of the final pieces and the stock material units, which in fact can be viewed as a knapsack constraint.\n",
    "\n",
    "$j \\in \\text{Pieces}$: Set of final pieces.\n",
    "\n",
    "#### Parameters\n",
    "\n",
    "$\\text{Requirement}_j \\in \\mathbb{N}$: Demand requirement of final piece $j$.\n",
    "\n",
    "$\\text{Frequency}_{p,j} \\in \\mathbb{N}$: Number of pieces of type $j$ cut out from pattern $p$.\n",
    "\n",
    "#### Decision Variables\n",
    "\n",
    "$\\text{count}_p \\in \\mathbb{N}$: Number of times pattern $p$ is used.\n",
    "\n",
    "#### Objective Function\n",
    "\n",
    "- **Material Consumption:** Minimize the number of stock material units used.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\text{Min} \\sum_{p \\in \\text{Patterns}}{\\text{count}_p}\n",
    "\\tag{2.0}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "#### Constraints\n",
    "\n",
    "- **Satisfy Demand:** Total number of final pieces of type $j$ obtained must satisfy its demand requirement.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\sum_{p \\in \\text{Patterns}}{\\text{Frequency}_{p,j} \\cdot \\text{count}_p} \\geq \\text{Requirement}_j \\quad \\forall j \\in \\text{Pieces}\n",
    "\\tag{2.1}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "Recall that the number of patterns grows exponentially with the number of final pieces, so in practice the Full Master Problem cannot be solved in one shot. Instead, we consider a Restricted Master Problem (RMP), initialized with a few trivial patterns. Then we follow an iterative approach, alternating between solving a knapsack problem (i.e. the subproblem) to generate a new pattern (i.e. the entering column) and solving a larger RMP to update the objective function — representing the reduced cost of the next pattern to be selected — of the subproblem. This cycle is repeated until the reduced cost of the entering column is non-negative.\n",
    "\n",
    "-----\n",
    "\n",
    "## Python Implementation\n",
    "\n",
    "In the following implementation of column generation, we use two main libraries:\n",
    "\n",
    "- Numpy for scientific computing.\n",
    "- Gurobi for mathematical optimization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "\n",
    "\n",
    "class MasterProblem:\n",
    "    def __init__(self):\n",
    "        self.model = gp.Model(\"master\")\n",
    "        self.vars = None\n",
    "        self.constrs = None\n",
    "        \n",
    "    def setup(self, patterns, demand):\n",
    "        num_patterns = len(patterns)\n",
    "        self.vars = self.model.addVars(num_patterns, obj=1, name=\"Pattern\")\n",
    "        self.constrs = self.model.addConstrs((gp.quicksum(patterns[pattern][piece]*self.vars[pattern]\n",
    "                                                          for pattern in range(num_patterns))\n",
    "                                              >= demand[piece] for piece in demand.keys()),\n",
    "                                             name=\"Demand\")\n",
    "        self.model.modelSense = GRB.MINIMIZE\n",
    "        # Turning off output because of the iterative procedure\n",
    "        self.model.params.outputFlag = 0\n",
    "        self.model.update()\n",
    "        \n",
    "    def update(self, pattern, index):\n",
    "        new_col = gp.Column(coeffs=pattern, constrs=self.constrs.values())\n",
    "        self.vars[index] = self.model.addVar(obj=1, column=new_col,\n",
    "                                             name=f\"Pattern[{index}]\")\n",
    "        self.model.update()\n",
    "\n",
    "\n",
    "class SubProblem:\n",
    "    def __init__(self):\n",
    "        self.model = gp.Model(\"subproblem\")\n",
    "        self.vars = {}\n",
    "        self.constr = None\n",
    "        \n",
    "    def setup(self, stock_length, lengths, duals):\n",
    "        self.vars = self.model.addVars(len(lengths), obj=duals, vtype=GRB.INTEGER,\n",
    "                                       name=\"Frequency\")\n",
    "        self.constr = self.model.addConstr(self.vars.prod(lengths) <= stock_length,\n",
    "                                           name=\"Knapsack\")\n",
    "        self.model.modelSense = GRB.MAXIMIZE\n",
    "        # Turning off output because of the iterative procedure\n",
    "        self.model.params.outputFlag = 0\n",
    "        # Stop the subproblem routine as soon as the objective's best bound becomes\n",
    "        #less than or equal to one, as this implies a non-negative reduced cost for\n",
    "        #the entering column.\n",
    "        self.model.params.bestBdStop = 1\n",
    "        self.model.update()\n",
    "        \n",
    "    def update(self, duals):\n",
    "        self.model.setAttr(\"obj\", self.vars, duals)\n",
    "        self.model.update()\n",
    "\n",
    "\n",
    "class CuttingStock:\n",
    "    def __init__(self, stock_length, pieces):\n",
    "        self.stock_length = stock_length\n",
    "        self.pieces, self.lengths, self.demand = gp.multidict(pieces)\n",
    "        self.patterns = None\n",
    "        self.duals = [0]*len(self.pieces)\n",
    "        piece_reqs = [length*req for length, req in pieces.values()]\n",
    "        self.min_rolls = np.ceil(np.sum(piece_reqs)/stock_length)\n",
    "        self.solution = {}\n",
    "        self.master = MasterProblem()\n",
    "        self.subproblem = SubProblem()\n",
    "        \n",
    "    def _initialize_patterns(self):\n",
    "        # Find trivial patterns that consider one final piece at a time,\n",
    "        #fitting as many pieces as possible into the stock material unit\n",
    "        patterns = []\n",
    "        for idx, length in self.lengths.items():\n",
    "            pattern = [0]*len(self.pieces)\n",
    "            pattern[idx] = self.stock_length // length\n",
    "            patterns.append(pattern)\n",
    "        self.patterns = patterns\n",
    "        \n",
    "    def _generate_patterns(self):\n",
    "        self._initialize_patterns()\n",
    "        self.master.setup(self.patterns, self.demand)\n",
    "        self.subproblem.setup(self.stock_length, self.lengths, self.duals)\n",
    "        while True:\n",
    "            self.master.model.optimize()\n",
    "            self.duals = self.master.model.getAttr(\"pi\", self.master.constrs)\n",
    "            self.subproblem.update(self.duals)\n",
    "            self.subproblem.model.optimize()\n",
    "            reduced_cost = 1 - self.subproblem.model.objVal\n",
    "            if reduced_cost >= 0:\n",
    "                break\n",
    "            \n",
    "            pattern = [0]*len(self.pieces)\n",
    "            for piece, var in self.subproblem.vars.items():\n",
    "                if var.x > 0.5:\n",
    "                    pattern[piece] = round(var.x)\n",
    "            self.master.update(pattern, len(self.patterns))\n",
    "            self.patterns.append(pattern)\n",
    "    def solve(self):\n",
    "        \"\"\"\n",
    "        Gurobi does not support branch-and-price, as this requires to add columns\n",
    "        at local nodes of the search tree. A heuristic is used instead, where the\n",
    "        integrality constraints for the variables of the final root LP relaxation\n",
    "        are installed and the resulting MIP is solved. Note that the optimal\n",
    "        solution could be overlooked, as additional columns are not generated at\n",
    "        the local nodes of the search tree.\n",
    "        \"\"\"\n",
    "        self._generate_patterns()\n",
    "        self.master.model.setAttr(\"vType\", self.master.vars, GRB.INTEGER)\n",
    "        self.master.model.optimize()\n",
    "        for pattern, var in self.master.vars.items():\n",
    "            if var.x > 0.5:\n",
    "                self.solution[pattern] = round(var.x)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Instance\n",
    "\n",
    "We now test our implementation using a toy example with 13 final pieces to be cut out from stock material units of 5,600 cm. The set of orders specifying the lengths and the demand requirements of final pieces is presented below:\n",
    "\n",
    "| ID | Final Piece Length (cm) | Demand (units)|\n",
    "|----|----|----|\n",
    "| 0 | 1380 | 22 |\n",
    "| 1 |  1520 | 25 |\n",
    "| 2 | 1560 | 12 |\n",
    "| 3 | 1710 | 14 |\n",
    "| 4 | 1820 | 18 |\n",
    "| 5 | 1880 | 18 |\n",
    "| 6 | 1930 | 20 |\n",
    "| 7 | 2000 | 10 |\n",
    "| 8 | 2050 | 12 |\n",
    "| 9 | 2100 | 14 |\n",
    "| 10 | 2140 | 16 |\n",
    "| 11 | 2150 | 18 |\n",
    "| 12 | 2200 | 20 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using license file c:\\gurobi\\gurobi.lic\n"
     ]
    }
   ],
   "source": [
    "# Dictionary that maps each final piece ID with their width and demand requirement\n",
    "orders = {0:[1380,22],\n",
    "          1:[1520,25],\n",
    "          2:[1560,12],\n",
    "          3:[1710,14],\n",
    "          4:[1820,18],\n",
    "          5:[1880,18],\n",
    "          6:[1930,20],\n",
    "          7:[2000,10],\n",
    "          8:[2050,12],\n",
    "          9:[2100,14],\n",
    "          10:[2140,16],\n",
    "          11:[2150,18],\n",
    "          12:[2200,20]}\n",
    "\n",
    "mycsp = CuttingStock(5600, orders)\n",
    "mycsp.solve()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The patterns generated are the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2],\n",
       " [0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0],\n",
       " [0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0],\n",
       " [1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0],\n",
       " [1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0],\n",
       " [0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],\n",
       " [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],\n",
       " [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0],\n",
       " [0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],\n",
       " [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0],\n",
       " [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],\n",
       " [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0],\n",
       " [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0],\n",
       " [0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],\n",
       " [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],\n",
       " [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0],\n",
       " [0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],\n",
       " [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],\n",
       " [0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],\n",
       " [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],\n",
       " [0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0],\n",
       " [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],\n",
       " [0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],\n",
       " [0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mycsp.patterns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The patterns that are actually used and their respective frequency are reported below:\n",
    "\n",
    "| Pattern ID | Frequency | Description |\n",
    "|----|----|----|\n",
    "| 4 | 1 | 3 units of final piece 4 |\n",
    "| 17 | 7 | 1 unit and 2 units of final pieces 0 and 9 |\n",
    "| 19 | 2 | 1 unit of final pieces 2, 5, and 10 |\n",
    "| 20 | 4 | 2 unit and 1 units of final pieces 3 and 10 |\n",
    "| 22 | 1 | 2 unit and 1 units of final pieces 3 and 11 | \n",
    "| 26 | 5 | 1 unit of final pieces 1, 5, and 10 |\n",
    "| 28 | 17 | 1 unit of final pieces 1, 6, and 11 |\n",
    "| 29 | 4 | 1 unit and 2 units of final pieces 4 and 5 |\n",
    "| 31 | 10 | 1 unit of final pieces 0, 7, and 12 |\n",
    "| 32 | 3 | 1 unit of final pieces 2, 6, and 8 |\n",
    "| 34 | 4 | 1 unit of final pieces 3, 4, and 8 |\n",
    "| 35 | 5 | 1 unit of final pieces 0, 8, and 10 |\n",
    "| 36 | 3 | 1 unit of final pieces 1, 5, and 12 |\n",
    "| 38 | 7 | 1 unit of final pieces 2, 4, and 12 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{4: 1, 17: 7, 19: 2, 20: 4, 22: 1, 26: 5, 28: 17, 29: 4, 31: 10, 32: 3, 34: 4, 35: 5, 36: 3, 38: 7}\n"
     ]
    }
   ],
   "source": [
    "print(mycsp.solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The minimum number of stock material units that must be used is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "73.0\n"
     ]
    }
   ],
   "source": [
    "print(mycsp.min_rolls)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The actual number of stock material units used by the solution found is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "73"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(mycsp.solution.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "This notebook showed how to implement delayed column generation using Gurobi in an object-oriented framework. It also suggested a heuristic that can be used in lieu of a branch-and-price scheme, in the event that this is not compatible with Gurobi. Finally, it's worth mentioning that the reader can improve the performance of this implementation by replacing the subproblem routine, which uses a MIP solver, with an algorithm specifically tailored for the Knapsack problem.\n",
    "\n",
    "-----\n",
    "\n",
    "## References\n",
    "\n",
    "1. Desaulniers, G., Desrosiers, J., & Solomon, M. M. (Eds.). (2006). Column generation (Vol. 5). Springer Science & Business Media.\n",
    "2. Kantorovich, L. V., & Zalgaller, V. A. (1951). Calculation of rational cutting of stock. Lenizdat, Leningrad, 5, 11-14.\n",
    "\n",
    "Copyright © 2021 Gurobi Optimization, LLC"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Edit Metadata",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
